← All Articles

[SW Expert Academy] 9092. 마라톤

Posted on

문제 :

승원이는 마라톤 동아리 “나는 마라토너다” 의 회장으로, 2018년 새해를 맞아 마라톤 대회를 열었다.

마라톤 코스는 n개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 2, 3, 4번 순서대로 모든 체크 포인트를 순서대로 방문한 후n번 체크포인트에서 끝나야지 마라톤이 끝난다.

각 체크포인트는 2차원 좌표평면의 정수 좌표로 주어지며, 두 체크포인트 간의 거리는 택시 거리로 계산된다. 즉, 두 점 (x1 , y1) 과 (x2 , y2) 간의 거리는|x1 - x2| + |y1 - y2|로 계산된다.

현수는 “나는 마라토너다” 의 동아리원이다. 처음에 현수는 굳은 마음가짐으로 대회 참가를 결심했지만, 막상 대회가 다가오니 달리기가 싫어졌다.

그래서 현수는 중간에 있는 체크포인트 k 개를 몰래 건너뛰려 한다.

단, 1번 체크포인트와 n번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

현수가 체크포인트를 최대 k개 건너뛰면서 달릴 수 있다면, 현수가 달려야 하는 최소 거리는 얼마일까?


입력 :

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 체크포인트의 수 n과 건너뛸 점의 수 k가 주어진다. ( 0 ≤ k < n ≤ 500 )

이후 n개의 줄에 두 정수 xi, yi가 주어진다. (xi, yi)가 번째 체크포인트의 위치임을 의미한다. (-1000 ≤ xi, yi ≤ 1000)


출력 :

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

현수가 체크포인트 k개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.



풀이 :

역시… DP 문제는 정말 감이 잘 안오는 것 같긴 하다.

DP 문제의 경우 불필요하게 반복되는 부분을 memorization을 통해 효과적으로 구현해야 하는데,

처음에는 해당 체크포인트에서 몇개를 건너뛰어서 오면 거리가 몇인지 저장하려고 했다.

하지만 생각보다 잘 구현되지 않았고, 재귀 방식으로 구현하면서 현재 체크포인트에서 도착점까지 뛰어넘을 수 있는 횟수가 몇 번 남았는지에 따라 최소거리를 저장하였다.

DP[][] 배열의 경우,

DP[k][n] : 현재 n번 째 체크포인트에 있는 경우, k개의 체크 포인트를 더 뛰어넘을 수 있을 때 최소 거리 저장

이라고 생각하고 memorization을 실행했다.

DP의 경우… 코드가 길지 않고 간단하지만 재귀 방식이나 memorization 방식을 떠올리는 것 자체가 쉽지 않은 것 같다..

연습 더 많이 하자!



코드 :

코드 보기/접기 
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#include<cstring>

#define pii pair<int, int>
#define MAX 987654321

using namespace std;
vector<pii> positions;
int n, jumpnums, dp[500][500];

int calculDist(int firidx, int secidx) {
    return abs(positions[firidx].first - positions[secidx].first) + abs(positions[firidx].second - positions[secidx].second);
}

int dpProcess(int remains, int curidx) {
    if(curidx == n - 1) return 0;
    if(dp[remains][curidx]) return dp[remains][curidx];
    
    dp[remains][curidx] = MAX;
    
    for(int k=0; k<=remains; k++) {
        if(curidx + k + 1 >= n)  break;
        int nextval = dpProcess(remains - k, curidx + k + 1);
        dp[remains][curidx] = min(dp[remains][curidx], nextval + calculDist(curidx, curidx + k + 1));
     }
    return dp[remains][curidx];
}

int testCase() {
    int fir, sec;
    positions.clear();
    memset(dp, 0, sizeof(dp));
    
    cin >> n >> jumpnums;
    
    for(int i=0; i<n; i++){
        cin >> fir >> sec;
        positions.emplace_back(fir, sec);
    }
    
    return dpProcess(jumpnums, 0);
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin>>T;

    for(test_case = 1; test_case <= T; ++test_case)
    {
        cout << '#' << test_case << ' ' << testCase() << '\n';
    }
    return 0;
}


AlgorithmalgorithmSW ExpertC++